#ifndef LEETCODE_CN_CPP_PROBLEMS_5_H
#define LEETCODE_CN_CPP_PROBLEMS_5_H

#include <string>
#include <vector>

using namespace std;

namespace problem_5
{

class Solution
{
public:
    // DP
    string DP(const string &s)
    {
        // dp[i][j]表示s[i...j]是否为回文串
        // dp[i][j]=(dp[i+1][j-1] && s[i] == s[j])
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int minI = 0, maxLen = 0;
        for (int len = 1; len <= s.size(); ++len)
        {
            for (int i = 0; i < s.size(); ++i)
            {
                int j = i + len - 1;
                dp[i][j] = (s[i] == s[j]);
                if (i + 1 < s.size() && j - 1 >= 0 && i + 1 < j - 1)
                {
                    dp[i][j] = dp[i][j] && dp[i + 1][j - 1];
                }
                if (dp[i][j] && len > maxLen)
                {
                    maxLen = len;
                    minI = i;
                }
            }
        }
        return s.substr(minI, maxLen);
    }

    // 中心扩展
    void __expand(const string &s, int &i, int &j)
    {
        while (i >= 0 && j < s.size() && s[i] == s[j])
        {
            --i, ++j;
        }
        i++, j--;
    }
    string Expand(const string &s)
    {
        int minI = 0, maxLen = 0;
        for (int c = 0; c < s.size(); ++c)
        {
            int i = c, j = c;
            __expand(s, i, j);
            if (j - i + 1 > maxLen)
            {
                maxLen = j - i + 1;
                minI = i;
            }
            if (c + 1 < s.size() && s[c] == s[c + 1])
            {
                i = c;
                j = c + 1;
                __expand(s, i, j);
                if (j - i + 1 > maxLen)
                {
                    maxLen = j - i + 1;
                    minI = i;
                }
            }
        }
        return s.substr(minI, maxLen);
    }
    string longestPalindrome(string s)
    {
        if (s.empty())
        {
            return {};
        }
        return Expand(s);
    }
};

} // namespace problem_5

#endif //LEETCODE_CN_CPP_PROBLEMS_5_H